package demo.practice.backtrack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Offer38 {


    public static void main(String[] args) {
        Offer38 offer38= new Offer38();
        offer38.permutation("aab");
    }
    List<String> list= new ArrayList<>();

    public String[] permutation(String s) {
        Map<Character,Integer> map= new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c,map.getOrDefault(c,0)+1);
        }

        backtrack(new StringBuffer(),map);
        String[] res= new String[list.size()];
        int i=0;
        for (String s1 : list) {
            res[i++]=s1;
        }
        return res;

    }


    public void   backtrack(StringBuffer sb,Map<Character,Integer> map){
        if(map.isEmpty()){
            list.add(sb.toString());
        }

        for (Map.Entry<Character, Integer> en : map.entrySet()) {
            StringBuffer sb2= new StringBuffer(sb);
            Character c = en.getKey();
            //Integer count = en.getValue();
            sb2.append(c);
            Map<Character,Integer> mapchild= new HashMap<>(map);
            if(mapchild.get(c)>1){
                mapchild.put(c,mapchild.get(c)-1);
            }else{
                mapchild.remove(c);
            }

            backtrack(sb2,mapchild);
        }
    }

}
